using System;
using System.Collections.Generic;
using System.Diagnostics;
using FineCollection.Intf;



namespace FineCollection.Const
{

    /// <summary>
    /// Constant collections manipulation.
    /// Contains static functions for manipulate with constant collections.
    /// </summary>
    /// <stereotype>service</stereotype>
    /// <remarks>
    /// <para>
    /// Functions of this class can work with both constant andmodifiable collections,
    /// but creates always constant collections.
    /// </para>
    /// </remarks>
    public static class CC
    {
        
        /// <summary>
        /// Sorts the specified items and returns an appropriate ordered set.
        /// </summary>
        /// <typeparam name="T">type of a collection item.</typeparam>
        /// <param name="items">array of items. Can be empty or even null.</param>
        /// <returns>the created set.
        ///     <para>
        ///        If the given argument is null, it returns null.
        ///        If the given argument is empty arraym it returns an empty set.
        ///     </para>
        /// </returns>
        public static RRandomSet<T> OrderSetOf<T>(params T[] items)
            where T: IEquatable<T>
        {
            if (items == null)
                return null;

            int n = items.Length;
            switch (n)
            {
            case 0:
                return ConstOrderZero<T>.zero;
            case 1:
                return new ConstOrderOne<T>(items[0]);
            case 2:
                return new ConstSortSet<T>(items[0], items[1]);
            default:
                return new ConstSortSet<T>(items);
            }
        }


        /// <summary>
        /// Sorts the specified items and returns an appropriate ordered set.
        /// Uses a custom comparator for sorting.
        /// </summary>
        /// <typeparam name="T">type of a collection item.</typeparam>
        /// <param name="comparer">custom comparer.</param>
        /// <param name="items">array of items. Can be empty or even null.</param>
        /// <returns>the created set.
        ///     <para>
        ///        If the given argument is null, it returns null.
        ///        If the given argument is empty arraym it returns an empty set.
        ///     </para>
        /// </returns>
        public static RRandomSet<T> OrderSetOf<T>(IComparer<T> comparer, params T[] items)
        {
            if (items == null)
                return null;

            int n = items.Length;
            switch (n)
            {
            case 0:
                return new ConstOrderZero<T>(comparer);
            case 1:
                return new ConstOrderOne<T>(items[0], comparer);
            default:
                return new ConstSortSet<T>(items, comparer);
            }
        }


        /// <summary>
        /// Sorts the given characters and returns an appropriate ordered set.
        /// </summary>
        /// <param name="chars">characters for the set; may be an empty array or null.</param>
        /// <returns>set of given characters.</returns>
        public static RRandomSet<char> OrderSetOfChar(params char[] chars)
        {
            if (chars == null || chars.Length == 0)
                return ConstOrderZero<char>.zero;

            if (chars.Length == 1)
                return new ConstOrderOne<char>(chars[0]);

            if (chars.Length == 2)
                return new ConstSortSet<char>(chars[0], chars[1]);

            return new ConstSortSet<char>(chars);
        }


        /// <summary>
        /// Sorts the characters given as a string, and returns an appropriate ordered set.
        /// </summary>
        /// <param name="chars">a string with characters for the set; may be an empty string or null.</param>
        /// <returns>set of given characters.</returns>
        public static RRandomSet<char> OrderSetOfChar(string chars)
        {
            if (chars == null || chars.Length == 0)
                return ConstOrderZero<char>.zero;

            if (chars.Length == 1)
                return new ConstOrderOne<char>(chars[0]);

            if (chars.Length == 2)
                return new ConstSortSet<char>(chars[0], chars[1]);

            if (chars.Length == 3)
                return new ConstSortSet<char>(chars[0], chars[1], chars[2]);

            return new ConstSortSet<char>(chars.ToCharArray());
        }


        /// <summary>
        /// Makes an appropriate set.
        /// </summary>
        /// <typeparam name="T">type of a collection item.</typeparam>
        /// <param name="items">array of items. Can be empty or even null.</param>
        /// <returns>the created set.
        ///     <para>
        ///        If the given argument is null, it returns null.
        ///        If the given argument is empty arraym it returns an empty set.
        ///     </para>
        ///     The result order is undefined.
        /// </returns>
        public static RSet<T> SetOf<T>(params T[] items)
            where T: IEquatable<T>
        {
            if (items == null)
                return null;

            int n = items.Length;

            if (n >= 2 && typeof(T).IsSubclassOf(typeof(IComparable<T>)))
                return OrderSetOf(Comparer<T>.Default, items);

            switch (n)
            {
            case 0:
                return ConstZero<T>.zero;
            case 1:
                return new ConstOne<T>(items[0]);
            default:
                if (n <= 5)
                    return new ConstTinySet<T>(items);
                else
                    return new Cont.HashSet<T>(items);
            }
        }


        /// <summary>
        /// Makes an appropriate set with the custom equator.
        /// </summary>
        /// <typeparam name="T">type of a collection item.</typeparam>
        /// <param name="equator">custom equator.</param>
        /// <param name="items">array of items. Can be empty or even null.</param>
        /// <returns>the created set.
        ///     <para>
        ///        If the given argument is null, it returns null.
        ///        If the given argument is empty arraym it returns an empty set.
        ///     </para>
        ///     The result order is undefined.
        /// </returns>
        public static RSet<T> SetOf<T>(IEqualityComparer<T> equator, params T[] items)
            where T: IEquatable<T>
        {
            if (items == null)
                return null;

            int n = items.Length;
            switch (n)
            {
            case 0:
                return new ConstZero<T>(equator);
            case 1:
                return new ConstOne<T>(items[0], equator);
            default:
                if (n <= 5)
                    return new ConstTinySet<T>(items, equator);
                else
                    return new Cont.HashSet<T>(items);
            }
        }



        /// <summary>
        /// Performs the union of the two ordered sets.
        /// </summary>
        /// <typeparam name="T">type of an item.</typeparam>
        /// <param name="set1">the first set (can be null or empty).</param>
        /// <param name="set2">the second set (can be null or empty).</param>
        /// <returns>constant union of the specified sets.</returns>
        /// <remarks>
        /// <para>
        /// The result set will contain all items that are present in both sets.
        /// So, the number of result items will be from <i>max(n1,n2)</i> to <i>n1 + n2</i>
        /// inclusive.
        /// </para>
        /// <para>
        /// This function implements a sorted merge algorithm (without sort -
        /// both sets are already ordered), 
        /// and the complexity of this method id <i>o(n)</i>,
        /// where <i>n</i> is a number of items in both sets.
        /// </para>
        /// <para>
        /// In case when one set includes another one, and the largest one
        /// is constant and ordered, this function returns the first one
        /// without making a copy.
        /// </para>
        /// </remarks>
        public static RRandomSet<T> Union<T>(ROrderSet<T> set1, ROrderSet<T> set2)
            where T: IComparable<T>
        {
            int n1 = set1 != null ? set1.Count : 0,
                n2 = set2 != null ? set2.Count : 0;

            if (n1 == 0 && n2 == 0)
            {
                return ConstOrderZero<T>.zero;
            }
            else if (n1 > 0 && n2 == 0)
            {
                if (set1 is RImmutable && set1 is RRandomSet<T>)
                    return set1 as RRandomSet<T>;
                else
                    return MakeAppropriateCopy(set1);
            }
            else if (n2 > 0 && n1 == 0)
            {
                if (set2 is RImmutable && set2 is RRandomSet<T>)
                    return set2 as RRandomSet<T>;
                else
                    return MakeAppropriateCopy(set2);
            }
            else
            {
                return Merge(set1, set2);
            }

        }


        private static RRandomSet<T> Merge<T>(ROrderSet<T> set1, ROrderSet<T> set2)
            where T : IComparable<T>
        {
            int n1 = set1.Count,
                n2 = set2.Count;
            int limit = n1 + n2,
                k = 0;

            T[] arr = new T[limit];

            RIterator<T> it1 = set1.TakeIterator(),
                         it2 = set2.TakeIterator();
            bool ex1 = it1.Next(),
                 ex2 = it2.Next();
            
            while (ex1 && ex2)
            {
                int z = Math.Sign( it1.Current.CompareTo(it2.Current) );
                switch (z)
                {
                    case -1:
                        arr[k++] = it1.Current;
                        ex1 = it1.Next();
                        break;
                    case +1:
                        arr[k++] = it2.Current;
                        ex2 = it2.Next();
                        break;
                    case 0:
                        arr[k++] = it1.Current;
                        ex1 = it1.Next();
                        ex2 = it2.Next();
                        break;
                }
            }

            while (ex1)
            {
                arr[k++] = it1.Current;
                ex1 = it1.Next();
            }

            while (ex2)
            {
                arr[k++] = it2.Current;
                ex2 = it2.Next();
            }

            RRandomSet<T> result;

            // if set1 contains all items of set2
            if (k == n1 && n1 >= n2 && set1 is RRandomSet<T>)
                result = set1 as RRandomSet<T>;
            // if set2 contains all items of set1
            else if (k == n2 && n2 >= n1 && set2 is RRandomSet<T>)
                result = set2 as RRandomSet<T>;
            // in other case
            else
                result = new ConstSortSet<T>(arr, k, true);

            return result;
        }


        /// <summary>
        /// Performs the intersection of two ordered sets.
        /// </summary>
        /// <typeparam name="T">type of an item.</typeparam>
        /// <param name="set1">the first set (can be null or empty).</param>
        /// <param name="set2">the second set (can be null or empty).</param>
        /// <returns>constant intersection of the specified sets.</returns>
        /// <remarks>
        /// <para>
        /// The result is a set where each item presents in both specified sets.
        /// So, the number of result items will be from <i>0</i> to <i>min(n1, n2)</i>
        /// inclusive.
        /// </para>
        /// <para>
        /// This method implements the optimized nested-loops with binary serach algorithm.
        /// Its complexity is <i>o( (m + 2) ln(n1 + n2) )</i>, where <i>m</i> is a number
        /// of items in the result set.
        /// </para>
        /// <para>
        /// In case when one set includes another one, and the largest one
        /// is constant and ordered, this function returns the first one
        /// without making a copy.
        /// </para>
        /// </remarks>
        public static RRandomSet<T> Intersect<T>(ROrderSet<T> set1, ROrderSet<T> set2)
            where T : IComparable<T>
        {
            int n1 = set1 != null ? set1.Count : 0,
                n2 = set2 != null ? set2.Count : 0;

            if (n1 == 0 || n2 == 0)
                return ConstOrderZero<T>.zero;

            return FastJoin(set1, set2);
        }


        private static RRandomSet<T> FastJoin<T>(ROrderSet<T> set1, ROrderSet<T> set2)
            where T : IComparable<T>
        {
            int n1 = set1.Count,
                n2 = set2.Count;
            int limit = Math.Min(n1, n2),
                rn = 0;
            
            T[] resultArray = null;

            // inner join

            ROrderIterator<T> it1 = set1.TakeIterator(),
                              it2 = set2.TakeIterator();
            it1.Next();
            it2.Next();

            while (it1.Where < +1 && it2.Where < +1) // while both are active
            {
                int z = Math.Sign( it1.Current.CompareTo(it2.Current) );
                switch(z)
                {
                    case 0:
                        if (resultArray == null)
                            resultArray = new T[limit];
                        resultArray[rn++] = it1.Current;
                        it1.Next();
                        it2.Next();
                        break;

                    case -1:
                        it1.Jump(it2.Current);
                        break;

                    case +1:
                        it2.Jump(it1.Current);
                        break;
                }
            }

            if (n1 == rn && set1 is RImmutable && set1 is RRandomSet<T>) // the result is exactly first set
                return set1 as RRandomSet<T>;
            if (n2 == rn && set2 is RImmutable && set2 is RRandomSet<T>) // the result is exactly second set
                return set2 as RRandomSet<T>;

            return MakeAppropriateCopy(resultArray, rn, true);
        }



        /// <summary>
        /// Performs the mathematical difference between the <c>minuend</c> 
        /// and the <c>subtrahend</c>. In other words, this functions returns 
        /// the set contains items from the <c>minuend</c> that don't present
        /// in the <c>subtrahend</c>.
        /// </summary>
        /// <typeparam name="T">type of an item.</typeparam>
        /// <param name="minuend">minuend of a difference.</param>
        /// <param name="subtrahend">subtrahend of a difference.</param>
        /// <returns>the difference.</returns>
        public static RRandomSet<T> Difference<T>(ROrderSet<T> minuend, ROrderSet<T> subtrahend)
            where T : IComparable<T>
        {
            int n1 = minuend != null ? minuend.Count : 0,
                n2 = subtrahend != null ? subtrahend.Count : 0;
            
            if (n1 == 0)
                return ConstOrderZero<T>.zero;

            if (n2 == 0)
            {
                if (minuend is RImmutable && minuend is RRandomSet<T>)
                    return minuend as RRandomSet<T>;
                else
                    return new ConstSortSet<T>(minuend);
            }

            Debug.Assert(minuend != null);
            Debug.Assert(minuend.IsNotEmpty);
            Debug.Assert(subtrahend != null);
            Debug.Assert(subtrahend.IsNotEmpty);
            

            // left anti-join

            int rn = 0;
            T[] diffArray = new T[n1];

            ROrderIterator<T> it1 = minuend.TakeIterator();
            ROrderIterator<T> it2 = subtrahend.TakeIterator();
            it1.Next();
            it2.Next();

            while (it1.Where < +1 && it2.Where < +1) // while both are active
            {
                int z = Math.Sign(it1.Current.CompareTo(it2.Current));
                switch (z)
                {
                    case 0:
                        it1.Next();
                        it2.Next();
                        break;

                    case -1:
                        diffArray[rn++] = it1.Current;
                        it1.Next();
                        break;

                    case +1:
                        it2.Jump(it1.Current);
                        break;
                }
            }

            return MakeAppropriateCopy(diffArray, rn, true);
        }


        private static RRandomSet<T> MakeAppropriateCopy<T>(ROrderSet<T> set)
            where T : IComparable<T>
        {
            int n = set.Count;
            switch (n)
            {
                case 0:
                    return ConstOrderZero<T>.zero;
                case 1:
                    return new ConstOrderOne<T>(set.First);
                default:
                    return new ConstSortSet<T>(set);
            }
        }


        // <param name="arr">must be a sorted array!</param>
        private static RRandomSet<T> MakeAppropriateCopy<T>(T[] arr, int count, bool takeOwnership)
            where T : IComparable<T>
        {
            if (count > 0)
                Debug.Assert(count <= arr.Length);

            switch (count)
            {
                case 0:
                    return ConstOrderZero<T>.zero;
                case 1:
                    return new ConstOrderOne<T>(arr[0]);
                default:
                    return new ConstSortSet<T>(arr, count, takeOwnership);
            }
        }


        /// <summary>
        /// Checks whether the specified collection contains at least one item of type <c>T2</c>.
        /// </summary>
        /// <typeparam name="T2">type of item to check (must be a subclass of <c>T1</c>).</typeparam>
        /// <typeparam name="T1">type of collection's items.</typeparam>
        /// <param name="col">collection to check throw.</param>
        /// <returns>found or not.</returns>
        public static bool HasItemOfType<T2,T1>(RCollection<T1> col)
            where T1: class
            where T2: class, T1
        {
            RIterator<T1> it = col.TakeIterator();
            while (it.Next())
                if (it.Current is T2)
                    return true;

            return false;
        }


        /// <summary>
        /// Selects items of type <c>T2</c> from the collection with items of type <c>T1</c>.
        /// </summary>
        /// <typeparam name="T2">type of desired items, must be a subtype of <c>T1</c>.</typeparam>
        /// <typeparam name="T1">type of collection's items.</typeparam>
        /// <param name="col">collection to select from.</param>
        /// <returns>list of found items; the order of them is the same 
        ///          as provided by the given collection iterator.</returns>
        public static RRandomList<T2> ListByType<T2,T1>(RCollection<T1> col)
            where T1: class
            where T2: class, T1
        {
            // first loop - count 
            int n = 0;
            RIterator<T1> it = col.TakeIterator();
            while (it.Next())
                if (it.Current is T2)
                    n++;

            // make appropriate copy
            RRandomList<T2> result;
            switch (n)
            {
            case 0:
                result = new ConstZero<T2>();
                break;

            case 1:
                RIterator<T1> it1 = col.TakeIterator();
                T2 obj = null;
                while (it1.Next() && obj == null)
                    if (it1.Current is T2)
                        obj = it1.Current as T2;
                result = new ConstOne<T2>(obj);
                break;

            default:
                T2[] arr = new T2[n];
                int k = 0;
                RIterator<T1> it2 = col.TakeIterator();
                while (it2.Next() && k < n)
                    if (it2.Current is T2)
                        arr[k++] = it2.Current as T2;
                ConstArray<T2> imar = new ConstArray<T2>(1, arr, n, true);
                result = imar;
                break;
            }

            // ok
            return result;
        }


        /// <summary>
        /// Compares two ordered sets for equality, with the default equator of the first set items.
        /// </summary>
        /// <typeparam name="T1">type of the first set items.</typeparam>
        /// <typeparam name="T2">type of the second set items, should be T1 or a subtype of T1.</typeparam>
        /// <param name="set1">the first set to compare.</param>
        /// <param name="set2">the second set to compare.</param>
        /// <returns>true if both sets are equal.</returns>
        public static bool AreEqual<T1, T2>(ROrderSet<T1> set1, ROrderSet<T2> set2)
            where T2: T1
        {
            IEqualityComparer<T1> equator = EqualityComparer<T1>.Default;
            return AreEqual(set1, set2, equator);
        }


        /// <summary>
        /// Compares two ordered sets for equality, with the custom equator.
        /// </summary>
        /// <typeparam name="T">supertype of items (in both sets).</typeparam>
        /// <typeparam name="T1">type of the first set items.</typeparam>
        /// <typeparam name="T2">type of the second set items.</typeparam>
        /// <param name="set1">the first set to compare.</param>
        /// <param name="set2">the second set to compare.</param>
        /// <returns>true if both sets are equal.</returns>
        public static bool AreEqual<T,T1,T2>(ROrderSet<T1> set1, ROrderSet<T2> set2, IEqualityComparer<T> equator)
            where T1: T
            where T2: T
        {
            int n1 = (set1 != null) ? set1.Count : 0,
                n2 = (set2 != null) ? set2.Count : 0;

            if (n1 == 0 && n2 == 0)
                return true;
            if (n1 != n2)
                return false;

            Debug.Assert(set1 != null && set2 != null);

            RIterator<T1> it1 = set1.TakeIterator();
            RIterator<T2> it2 = set2.TakeIterator();

            it1.Next();
            it2.Next();

            while (it1.Where < +1 && it2.Where < +1)
            {
                if (! equator.Equals(it1.Current, it2.Current))
                    return false;

                it1.Next();
                it2.Next();
            }

            if (it1.Where != it2.Where)
                return false;

            return true;
        }

    }


}